package LC;

import javafx.util.Pair;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @ClassName LC1091
 * @Description: TODO
 * @Author hl
 * @Date 2020/8/13
 * @Version V1.0
 **/
public class LC1091 {
    public static void main(String[] args) {
        int[][] grid={{0,1},{1,0}};
        System.out.println(shortestPathBinaryMatrix(grid));

    }
    public static int shortestPathBinaryMatrix(int[][] grid) {
        Queue<Pair<Integer,Integer>> queue=new LinkedList<>();
        int[][]arrs={{0,1},{0,-1},{-1,0},{1,0},{-1,1},{1,-1},{-1,-1},{1,1}};
        int n=grid.length;
        int m=grid[0].length;
        int [][] visited=new int[n][m];
        int step=0;
        queue.add(new Pair<>(0,0));
        while(!queue.isEmpty()){
            step++;
            int size=queue.size();
            while(size-->0){
               Pair<Integer,Integer> pair=queue.poll();
               int R=pair.getKey();
               int C=pair.getValue();
                if(R<0||C<0||R>=n||C>=m||grid[R][C]==1){
                    continue;
                }
                if(R==n-1&&C==m-1){
                    return step;
                }
                grid[R][C]=1;
               for(int []arr:arrs){
                   int Rarr=arr[0]+R;
                   int Crr=arr[1]+C;
                   if(Rarr<0||Crr<0||Rarr>=n||Crr>=m||grid[Rarr][Crr]==1){
                       continue;
                   }
                   if(Rarr==n-1&&Crr==m-1){
                       return step+1;
                   }
                   grid[Rarr][Crr]=1;
               }
            }
        }
        return  -1;
    }
}
